In a magnetic storage channel it is desirable to limit the number of consecutive zeroes in a data stream in order to ensure frequent updates to the timing recovery system. This is called run length limitation and may be accomplished, for example, by dividing the data into “N” bit blocks, then mapping each block onto N+1 bit blocks chosen such that no N+1 bit blocks, nor pair of concatenated blocks, has more than a desired number “k” of consecutive zeroes. Typical codes include those replacing each block of eight bits with a run-length-limited (“RLL”) block of nine bits (“8/9 code”), as well as “16/17”, “24/25”, “32/33”, and others. The ratio N/(N+1) is called the “rate” of the code. Of course, RLL schemes with different coding rates also exist.
A disadvantage of many prior art methods is that they are defined by look-up tables, so that encoding and decoding complexity, together with cost and power consumption, increase exponentially with code length. Another disadvantage is that most prior art methods are ad hoc, requiring a different approach to develop a code for each rate. Some prior art methods can be efficiently encoded and decoded using sequential logic thus partially addressing the complexity problem. However, these prior art methods often require considerable ingenuity to adapt them to a given rate and rates exist for which no code can be constructed using them. This is a concern because as recording technology moves away from byte-oriented error correction (such as Reed-Solomon codes) to soft-decoding methods (such as Turbo and low density parity check (“LDPC”) codes), RLL codes with a variety of rates will be required. Additionally, some prior art methods for constructing long codes have been devised which involve interleaving un-encoded blocks with blocks from a shorter, RLL-encoded word. While general in some sense, these techniques often give rise to severely sub-optimal values of k.
In view of the foregoing, a need exists in the art for a general method for the construction of RLL codes which employs efficient encoders and decoders; produces codes with near-optimal values of k; and easily adapts to any desired code rate.